package com.wuyou.mid;

import sun.awt.windows.ThemeReader;

/**
 * 最大二叉树 II
 */
public class InsertIntoMaxTree {


    public TreeNode solution_1(TreeNode root, int val) {
        TreeNode treeNode = new TreeNode(val);
        if (root.val < val) {
            treeNode.left = root;
            return treeNode;
        }
        TreeNode res = root;
        if (root.right != null) {
            while (root.right.val > val) {
                root = root.right;
                if (root.right == null) {
                    break;
                }
            }
        }
        TreeNode right = root.right;
        root.right = treeNode;
        treeNode.left = right;
        return res;
    }

    public TreeNode recursionHandle(TreeNode root, int val) {
        TreeNode treeNode = new TreeNode(val);
        if (root.val < val) {
            treeNode.left = root;
            return treeNode;
        }
        if (root.right == null) {
            root.right = treeNode;
            return root;
        }
        if (root.right.val > val) {
            TreeNode treeNode1 = recursionHandle(root.right, val);
            return root.right = treeNode1;
        }
        TreeNode right = root.right;
        root.right = treeNode;
        treeNode.right = right;
        return root;
    }
}
